\begin{problem}{Циклические суффиксы}{cyclic.in}{cyclic.out}{2 секунды}{64 мебибайта}{C2}

Рассмотрим строку $S = s_1 s_2 s_3 \ldots s_{n - 1} s_n$ над алфавитом
$\Sigma$. {\it Циклическим расширением} порядка $m$ строки $S$ назовем
строку $s_1 s_2 s_3 \ldots s_{n - 1} s_n s_1 s_2 \ldots$ из $m$ символов;
это значит, что мы приписываем строку $S$ саму к себе, пока не получим требуемую длину,
и берем префикс длины $m$.

{\it Циклической строкой $\tilde S$} назовем бесконечное циклическое расширение 
строки $S$.

Рассмотрим суффиксы циклической строки $\tilde S$. Очевидно, существует не более
$|S|$ различных суффиксов: $(n + 1)$-ый суффикс совпадает с первым, $(n + 2)$-ой 
совпадает со вторым, и так далее. Более того, различных суффиксов может быть даже меньше.
Например, если $S = \t{abab}$, первые четыре суффикса циклической строки $\tilde S$ --- это:
\begin {eqnarray*}
\tilde S_1 & = & \t {ababababab} \ldots \\             
\tilde S_2 & = & \t {bababababa} \ldots \\
\tilde S_3 & = & \t {ababababab} \ldots \\
\tilde S_4 & = & \t {bababababa} \ldots
\end {eqnarray*}
Здесь существует всего два различных суффикса, в то время как $|S| = 4$.

Отсортируем первые $|S|$ суффиксов $\tilde S$ лексикографически. Если два суффикса совпадают,
первым поставим суффикс с меньшим индексом. Теперь нас интересует следующий вопрос:
на каком месте в этом списке стоит сама строка $\tilde S$?

Например, рассмотрим строку $S = \t {cabcab}$:
\begin {eqnarray*}
(1) \hskip 1cm \tilde S_2 & = & \t {abcabcabca} \ldots \\
(2) \hskip 1cm \tilde S_5 & = & \t {abcabcabca} \ldots \\
(3) \hskip 1cm \tilde S_3 & = & \t {bcabcabcab} \ldots \\
(4) \hskip 1cm \tilde S_6 & = & \t {bcabcabcab} \ldots \\
(5) \hskip 1cm \tilde S_1 & = & \t {cabcabcabc} \ldots \\
(6) \hskip 1cm \tilde S_4 & = & \t {cabcabcabc} \ldots
\end {eqnarray*}
Здесь циклическая строка $\tilde S = \tilde S_1$ находится на пятом месте.

Вам дана строка $S$. Ваша задача --- найти позицию циклической строки $\tilde S$ в описанном порядке.

\InputFile

Во входном файле записана единственная строка $S$ ($1 \le |S| \le 1 \, 000 \, 000$),
состоящая из прописных латинских букв.

\OutputFile

В выходной файл выведите единственное число --- номер строки
$\tilde S$ в описанном порядке среди первых $|S|$ суффиксов.

\Examples

\begin{example}
\exmp{
abracadabra
}{
3
}%
\exmp{
cabcab
}{
5
}%
\end{example}

\end{problem}
